public class Solution {
    public void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int mid = partition(arr, low, high);
            quickSort(arr, low, mid - 1);
            quickSort(arr, mid + 1, high);
        }
    }

    private int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 选择最后一个元素作为基准
        int slow = low; // 慢指针，用于跟踪小于基准的元素的最后一个位置

        for (int fast = low; fast < high; fast++) { // 从low到high-1进行遍历
            if (arr[fast] < pivot) {
                swap(arr, fast, slow); // 如果当前元素小于基准，交换fast和slow指向的元素
                slow++; // 移动慢指针
            }
        }
        swap(arr, high, slow); // 将基准元素放到正确的位置
        return slow; // 返回基准元素的新位置
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
